#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void traverse(int *arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void partition(int *arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int i = left, j = right;
    while (i < j)
    {
        while (i < j && arr[j] >= arr[left])
        {
            j--;
        }
        while (i < j && arr[left] >= arr[i])
        {
            i++;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    int temp = arr[left];
    arr[left] = arr[i];
    arr[i] = temp;
    printf("%d\n", i);
    traverse(arr, 8);
    partition(arr, left, i - 1);
    partition(arr, i + 1, right);
    // if (i - 1 > left)
    //     partition(arr, left, i - 1);
    // if (i + 1 < right)
    //     partition(arr, i + 1, right);
}
int main()
{
    // int arr[] = {1, 5, 3, 7, 9, 2, 4, 6, 8};
    int arr[] = {9, 3, 4, 7, 6, 8, 1, 2};
    partition(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
    traverse(arr, sizeof(arr) / sizeof(arr[0]));
}